// 5. 最长回文子串
// https://leetcode.cn/problems/longest-palindromic-substring/description/
// 思路 动态规划


/**
示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：

输入：s = "cbbd"
输出："bb"
 */

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
	let longestStr = '';
	let maxLength = -Infinity;
	if (s.length <= 1) {
		return s;
	}

	// 定义DP数组 dp[i,j] 为下标从i到j是否为回文串，是为true，否为false
	// i始终<=j, 所以DP数组不需要每个值都轮询到，只需要i<=j的那些就可以，即dp矩阵的右上方三角形

	/**
	 * DP矩阵示意
	 * 为1的部分是需要赋值的，为0的地方不需要
	   j
	 i 1 1 1 1 1
	 * 0 1 1 1 1 
	 * 0 0 1 1 1 
	 * 0 0 0 1 1
	 * 0 0 0 0 1
	 */

	// dp[i,j] = dp[i+1,j-1] && s[i] === s[j]
	// 根据这个推演公式，应该从后往前遍历

	// dp数组初始化
	// 初始化时，将对角线上的元素设置为true
	let dp = new Array(s.length).fill(0).map((_, row) => {
		return new Array(s.length).fill(0).map((_, col) => col === row);
	})

	longestStr = 0;
	maxLength = 1;

	for (let i = s.length - 1; i >= 0; i--) {
		for (let j = s.length - 1; j > i; j--) {
			const len = j - i + 1;
			if (len < maxLength) break;

			if ((i + 2) > j) {
				dp[i][j] = s[i] === s[j]
			} else {
				dp[i][j] = s[i] === s[j] && (dp[i + 1][j - 1] ? true : false);
			}

			if (dp[i][j]) {
				if (len >= maxLength) {
					maxLength = len;
					longestStr = i;

					// console.log(`${s} update: ${i}->${j} ${longestStr}`);
				}
			}
		}
	}

	// console.table(dp)
	return s.substring(longestStr, longestStr + maxLength);
};
console.log(`${'-'.repeat(20)}`)
console.log(longestPalindrome('a')); // a
console.log(longestPalindrome('babad')); // bab 或 aba
console.log(longestPalindrome('cbbd')); // bb